

import java.util.*;

/**
 * @program: 1.17二叉树
 * @description:
 * @author: 李鑫月
 * @create: 2022-01-17 09:47
 **/
 class BTNode {
    public int  val;
    public BTNode left;
    public  BTNode right;
    public BTNode(){
       ;
    }
    public BTNode(char val){
      this.val=val;
    }

}
public class BinaryTree{
   public BTNode root;
   public  BTNode creatTree(){
      BTNode A=new BTNode('A');
      BTNode B=new BTNode('B');
      BTNode C=new BTNode('C');
      BTNode D=new BTNode('D');
      BTNode E=new BTNode('E');
      BTNode F=new BTNode('F');
      BTNode G=new BTNode('G');
//      BTNode H=new BTNode('H');
      A.left=B;
      A.right=C;
      B.left=D;
      B.right=E;
      C.left=F;
      C.right=G;
//      E.right=H;
      return  A;
   }

   /**
    * 前序遍历递归
    * @param root
    */
   public void preOrder(BTNode root){
      if(root==null){
         System.out.print("NULL->");
         return;
      }
      //第一次来到此节点
      System.out.print(root.val+"->");
      preOrder(root.left);
      preOrder(root.right);
   }

   /**
    * 前序遍历迭代
    * @param root
    */
   public List<Integer> preOrder2(BTNode root){
      Stack<BTNode> stack=new Stack<>();
      List<Integer> res = new ArrayList<Integer>();

      if(root!=null){
         stack.push(root);
      }
      while (!stack.empty()){
         BTNode top=stack.pop();
         res.add(top.val);
         if(top.right!=null)stack.push(top.right);
         if(top.left!=null)stack.push(top.left);
      }
      return res;
   }

   /**
    * 前序遍历迭代
    * @param root
    * @return
    */
   public List<Integer> preOrder3(BTNode root){
      Stack<BTNode> stack=new Stack<>();
      List<Integer> res = new ArrayList<Integer>();
      BTNode cur=root;
      if(root==null){
         return res;
      }
      // 同时满足root为null及stack为空，才将结果返回
      while (!stack.empty()||cur!=null){
         // root不为null时入栈，向left方向推进直到叶子节点
         while(cur!=null){
            stack.push(cur);
            res.add(cur.val);
            cur=cur.left;
         }
         // 向left推进到叶子节点后弹出该叶子节点
         BTNode top=stack.pop();
         // 左子树遍历完毕，回到该节点,向right推进.
         cur=top.right;
      }
      return res;
   }
   /**
    * 前序遍历morris
    * * @param root
    * @return
    */
   public void preOrder4(BTNode root){
      BTNode pred=null;
      BTNode cur=root;
      if(root==null) return;
      while (cur!=null){
         pred=cur.left;
         //cur有左子树，能来到此节点二次
         if(pred!=null){
            //寻找此节点的前驱节点，即其左子树上的最右节点pred
           while (pred.right!=null&&pred.right!=cur){
              pred=pred.right;
           }
           //第一次来到此节点
           if(pred.right==null){
              System.out.print(cur.val+"->");
              pred.right=cur;
              cur=cur.left;
              continue;
           }
           //第二次来到此节点，说明此节点的左子树都已经遍历过了
           else {
              pred.right=null;
              cur=cur.right;
           }
         }
         //cur没有左子树，只来到此节点一次
         else {
            System.out.print(cur.val+"->");
            cur=cur.right;
         }
      }
      System.out.println();
   }
   /**
    * 中序遍历递归
    * @param root
    */
   public void InOrder(BTNode root){
      if(root==null){
         System.out.print("NULL->");
         return;
      }

      InOrder(root.left);
      //第二次来到此节点
      System.out.print(root.val+"->");
      InOrder(root.right);
   }
   /**
    * 中序遍历迭代2
    * @param root
    */
   public List<Integer> InOrder2(BTNode root){
      Stack<BTNode> stack=new Stack<>();
      List<Integer> res = new ArrayList<Integer>();
      if(root==null) return res;
      BTNode cur=root;
      while (!stack.empty()||cur!=null){
         while (cur!=null){
            stack.push(cur);
            cur=cur.left;
         }
         BTNode top=stack.pop();
         res.add(top.val);
         cur=cur.right;
      }
      return  res;
   }

   /**
    * 中序遍历morris
    * @param root
    */
   public void inOrder4(BTNode root){
      BTNode pred=null;
      BTNode cur=root;
      if(root==null) return;
      while (cur!=null){
         pred=cur.left;
         //cur有左子树，能来到此节点二次
         if(pred!=null){
            //寻找此节点的前驱节点，即其左子树上的最右节点pred
            while (pred.right!=null&&pred.right!=cur){
               pred=pred.right;
            }
            //第一次来到此节点
            if(pred.right==null){

               pred.right=cur;
               cur=cur.left;
               continue;
            }
            //第二次来到此节点，说明此节点的左子树都已经遍历过了
            else {
               System.out.print(cur.val+"->");
               pred.right=null;
               cur=cur.right;
            }
         }
         //cur没有左子树，只来到此节点一次
         else {
            System.out.print(cur.val+"->");
            cur=cur.right;
         }
      }
      System.out.println();
   }

   /**
    * 后序遍历递归
    *
    * @param root
    */
   public void PostOrder(BTNode root){
      if(root==null){
         System.out.print("NULL->");
         return;
      }

      PostOrder(root.left);
      PostOrder(root.right);
      System.out.print(root.val+"->");
   }
   /**
    * 后序遍历迭代
    *
    * @param root
    */
   public List<Integer> postOrder2(BTNode root){
      Stack<BTNode> stack=new Stack<>();
      List<Integer> res = new ArrayList<Integer>();
      if(root==null) return res;
      BTNode cur=root;
      BTNode pre=null;
      while (!stack.empty()||cur!=null){
         while (cur!=null){
            stack.push(cur);
            cur=cur.left;
         }
         BTNode top=stack.peek();
         if(top.right==null||top.right==pre){
            stack.pop();
            res.add(top.val);
            pre=top;
         }else {
            cur=cur.right;
         }
      }
      return  res;
   }
   /**
    * 后序遍历迭代
    *
    * @param root
    */
   public List<Integer> postOrder3(BTNode root){
      Stack<BTNode> stack=new Stack<>();
      List<Integer> res = new ArrayList<Integer>();
      if(root==null) return res;
      BTNode cur=root;
     stack.push(cur);
      while (!stack.empty()){
        BTNode top=stack.pop();
        res.add(top.val);
        if(top.left!=null)stack.push(top.left);
        if(top.right!=null)stack.push(top.right);
      }
      Collections.reverse(res);
      return  res;
   }
   /**
    * 后序遍历morris
    * @param root
    */
   public void postOrder4(BTNode root){
      BTNode pred=null;
      BTNode cur=root;
      if(root==null) return;
      while (cur!=null){
         pred=cur.left;
         //cur有左子树，能来到此节点二次
         if(pred!=null){
            //寻找此节点的前驱节点，即其左子树上的最右节点pred
            while (pred.right!=null&&pred.right!=cur){
               pred=pred.right;
            }
            //第一次来到此节点
            if(pred.right==null){

               pred.right=cur;
               cur=cur.left;
               continue;
            }
            //第二次来到此节点，说明此节点的左子树都已经遍历过了
            else {

               pred.right=null;
               print(cur.left);
               cur=cur.right;
            }
         }
         //cur没有左子树，只来到此节点一次
         else {

            cur=cur.right;
         }
      }
      print(root);

   }
   //逆序打印出此节点左子树的右边界，打印完要逆置回来
   public void print(BTNode head){
      BTNode tail=reverseEdge(head);
      BTNode cur=tail;
      while (cur!=null){
         System.out.print(cur.val+"->");

         cur=cur.right;
      }

      reverseEdge(tail);
   }
   //类似于单链表的逆置
   public BTNode reverseEdge(BTNode head){
      BTNode pre=null;
      BTNode next=null;
      while (head!=null){
         next=head.right;
         head.right=pre;

         pre=head;
         head=next;

      }
      return pre;
   }
   //// 遍历思路-求结点个数
   int count=0;
   public  int  getSize(BTNode root){
      if(root==null){
         return 0;
      }
      count++;
       getSize(root.left);
      getSize(root.right);
      return count;

   }
//// 子问题思路-求结点个数
   public  int  getSize1(BTNode root){
      int count=0;
      if(root==null){
         return 0;
      }
      int left=getSize1(root.left);
      int right=getSize1(root.right);
      return left+right+1;

   }

   // 子问题思路-求叶子结点个数
   public int  getLeafSize1(BTNode root){

      if(root==null){
         return 0;
      }
      if(root.left==null&&root.right==null){
         return 1;
      }

      int left=getLeafSize1(root.left);
      int right=getLeafSize1(root.right);
      return left+right;
   }
   // 遍历思路-求叶子结点个数
   int leafcount=0;
   public int  getLeafSize(BTNode root){

      if(root==null){
         return 0;
      }
      if(root.left==null&&root.right==null){
         leafcount++;
      }

      getLeafSize(root.left);
      getLeafSize(root.right);
      return leafcount;
   }
   int Max(int a,int b){
      return (a>b? a:b);
   }
   // 获取二叉树的高度
   int getHeight(BTNode root){
      int height=0;
      if(root==null){
         return 0;
      }
//      if(root.left==null&&root.right==null){
//         return 1;
//      }
      int left=getHeight(root.left);
      int right=getHeight(root.right);
      return  Max(left,right)+1;

   }
   // 子问题思路-求第 k 层结点个数
   int getKLevelSize(BTNode root,int k){
      if(root==null){
         return 0;
      }
      if(k==1){
         return 1;
      }

      return (getKLevelSize(root.left,k-1)+getKLevelSize(root, k-1));

   }
   // 查找 val 所在结点，没有找到返回 null
// 按照 根 -> 左子树 -> 右子树的顺序进行查找
// 一旦找到，立即返回，不需要继续在其他位置查找
   BTNode find(BTNode root,char val){
         if(root==null){
            return null;
         }
         if(root.val==val){
            return root;
         }
      BTNode left= find(root.left,val);
         if(left==null){
            BTNode right=find(root.right,val);
              return right;
         }else{
            return left;
         }
   }
   // 判断一棵树是不是完全二叉树
   boolean isCompleteTree(BTNode root){
      if(root == null) return true;
      Queue<BTNode> queue = new LinkedList<>();
      queue.offer(root);
      while (!queue.isEmpty()){
         BTNode ret=queue.poll();
         if(ret!=null){
            queue.offer(ret.left);
            queue.offer(ret.right);
         }else {
           break;
         }
      }
      while (!queue.isEmpty()){
         BTNode ret=queue.peek();
         if(ret!=null){
            return false;
         }
         queue.poll();
      }
      return true;



   }
   boolean isCompleteTree1(BTNode root){
      if(root==null){
         return true;
      }
      Queue<BTNode> queue=new LinkedList<>();
      queue.offer(root);
      while (!queue.isEmpty()){
        BTNode ret= queue.poll();
        if(ret!=null){
           queue.offer(ret.left);
           queue.offer(ret.right);
        }else {
           break;
        }
      }
      while (!queue.isEmpty()){
         if(queue.poll()!=null){
            return false;
         }
      }
      return true;

   }


   public BTNode mergeTrees(BTNode root1, BTNode root2) {
      BTNode node=new BTNode();
      if(root1==null&&root2==null){
         return null;
      }
      if(root1==null&&root2!=null){
         return root2;
      }
      if(root1!=null&&root2==null){
         return root1;
      }
      node.val=root1.val+root2.val;
      node.left=mergeTrees(root1.left,root2.left);
      node.right=mergeTrees(root1.right,root2.right);
      return node;

   }
   public void levelOrder(BTNode root){
      Queue<BTNode> queue=new LinkedList<>();

      if (root!=null){
         queue.offer(root);
      }else {
         return;
      }
      while (!queue.isEmpty()){
         BTNode tmp=queue.poll();
         System.out.print(tmp.val+" ");
         if(tmp.left!=null&&tmp.right!=null){
            queue.offer(tmp.left);
            queue.offer(tmp.right);
         }
      }



   }

   /**
    * 求二叉树根节点到指定节点的路径
    * @param node
    * @param target
    * @param path
    * @return
    */
   public  boolean getPathToTarget(BTNode node, BTNode target,
                                         LinkedList<BTNode> path) {
      if (node == null)
         return false;

      path.push(node);

      if (node == target)
         return true;
      // find in left tree
      if (getPathToTarget(node.left, target, path))
         return true;
      // find in right tree
      if (getPathToTarget(node.right, target, path))
         return true;

      // this node is not in the path of target
      // cause leftchild rightchild and itself do not have target node
      path.pop();
      return false;
   }








}
